import java.util.Arrays;
import java.util.Stack;

public class Test {

    public static void main(String[] args) {
        int[] arr={11,7,4,9,18,17,21,2,8,5};
        int[] arr1= Arrays.copyOf(arr,arr.length);
        System.out.println(Arrays.toString(arr1));
        //insertSort(arr1);
        //shellSort(arr1);
        //selectSort2(arr1);
        //heapSort(arr1);
        //bubbleSort(arr1);
        //quickSort(arr1);
        //quickSortnot(arr1);
        //mergeSort(arr1);
        mergeSortnor(arr1);
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 插入排序
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 场景：当前有一组数据 基本上趋于有序 那么就可以使用直接插入排序
     * 优点：越有序越快
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp=array[i];
            int j=i-1;
            for (;j>=0;j--){
                //if(array[j]>=temp)该排序就不稳定了
                if (array[j]>temp){
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=temp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度：O(logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap=gap/3+1;
            shell(array,gap);
        }
    }

    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int temp=array[i];
            int j=i-gap;
            for (;j>=0;j-=gap){
                if (array[j]>temp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=temp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度：和数据是否有序无关。均是O(N^2)
     * 空间复杂度： O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length ; j++) {
                if (array[minIndex]>array[j]){
                    minIndex=j;
                }
            }
            int cur=array[i];
            array[i]=array[minIndex];
            array[minIndex]=cur;
        }
    }

    public static void selectSort2(int[] array){
        int left=0;
        int right=array.length-1;
        while(left<right) {
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <= right; i++) {
                if (array[i]<array[minIndex]){
                    minIndex=i;
                }
                if (array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,minIndex,left);
            if (maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    public static void swap(int[] arr,int a,int b){
        int cur=arr[a];
        arr[a]=arr[b];
        arr[b]=cur;
    }

    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param arr
     */
    public static void heapSort(int[] arr){
        makebigHeap(arr);
        int end=arr.length-1;
        while(end>=0){
            swap(arr,0,end);
            siftDown(0,arr,end);
            end--;
        }
    }

    public static void makebigHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2; parent >=0; parent--) {
            siftDown(parent,arr,arr.length);
        }
    }

    public static void siftDown(int parent,int[] arr,int end){
        int child=parent*2+1;
        while(child<end){
            if (child+1<end&&arr[child+1]>arr[child]){
                child++;
            }
            if (arr[child]>arr[parent]){
                swap(arr,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度：
     * 不管数据 有序 还是无序 在不优化的情况下：O(N^2) 5 4 3 2 1
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 目前学到现在为止：2个稳定排序 ，插入排序 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            //在优化了的情况下，当数据有序，1 2 3 4 5
            //时间复杂度为：O(N)
            if (flag==false){
                break;
            }
        }
    }



    /**
     * 快速排序 优化
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(logN)
     * 稳定性：不稳定
     * @param arr
     */
    public static void quickSort(int arr[]){
        quick(arr,0,arr.length-1);
    }

    public static void quick(int[] arr,int start,int end){
        if (start>=end){
            return;
        }

        //优化
        if(end - start + 1 <= 10) {
            //插入排序
            insertSortRange(arr,start,end);
            return;
        }

        //三数取中
        int index = midThreeNum(arr,start,end);
        swap(arr,index,start);

        //寻找基准元素
        int par=partitionPrev(arr,start,end);

        quick(arr,start,par-1);
        quick(arr,par+1,end);
    }

    public static void insertSortRange(int[] arr,int left,int right){
        for (int i = left+1; i <= right; i++) {
            int temp=arr[i];
            int j=i-1;
            for (; j >=left ; j--) {
                if (arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }

    /**
     * 三位取中
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int midThreeNum(int[] arr,int left,int right){
        int mid=(left+right)/2;
        if (arr[left]<arr[right]){
            if (arr[mid]<arr[left]){
                return left;
            }else if(arr[mid]>arr[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if (arr[mid]<arr[right]){
                return right;
            }else if(arr[mid]>arr[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

    /**
     * 挖坑法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partitionDig(int[] arr,int left,int right){
        int temp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=temp){
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=temp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=temp;
        return left;
    }

    /**
     * Hoare法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partitionHoare(int[] arr,int left,int right){
        int i=left;
        int temp=arr[left];
        while(left<right){
            while(left<right&&arr[right]>=temp){
                right--;
            }
            while(left<right&&arr[left]<=temp){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,left,i);
        return left;
    }

    /**
     * 前后指针法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int partitionPrev(int[] arr,int left,int right){
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            if (arr[cur]<arr[left]&&arr[++prev]!=arr[cur]){
                swap(arr,cur,prev);
            }
        }
        swap(arr,left,prev);
        return prev;
    }

    /**
     * 非递归实现快速排序
     * @param arr
     */
    public static void quickSortnot(int[] arr){
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=arr.length-1;
        int par=partitionHoare(arr,left,right);
        if (par>left+1){
            stack.push(left);
            stack.push(par-1);
        }
        if (par<right-1){
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.empty()){
            right=stack.pop();
            left=stack.pop();
            par=partitionHoare(arr,left,right);
            if (par>left+1){
                stack.push(left);
                stack.push(par-1);
            }
            if (par<right-1){
                stack.push(par+1);
                stack.push(right);
            }
        }
    }


    /**
     * 归并排序
     * 时间复杂度：0(N * logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定的排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortfun(arr,0,arr.length-1);
    }

    public static void mergeSortfun(int[] arr,int left,int right){
        if (left>=right){
            return;
        }
        int mid=(left+right)/2;

        mergeSortfun(arr,left,mid);
        mergeSortfun(arr,mid+1,right);

        //合并
        merge(arr,left,right,mid);
    }

    public static void merge(int[] arr,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int k=0;
        int[] temp=new int[right-left+1];

        //要考虑相等
        while(s1<=e1&&s2<=e2){
            if (arr[s1]>arr[s2]){
                temp[k++]=arr[s2++];
            }else{
                temp[k++]=arr[s1++];
            }
        }

        while(s1<=e1){
            temp[k++]=arr[s1++];
        }

        while(s2<=e2){
            temp[k++]=arr[s2++];
        }
        //至此，temp数组中的所有元素已然有序
        //接下来把tmp数组的内容 拷贝到array数组当中

        //最后k=temp.length
        for (int i = 0; i < k; i++) {
            arr[i+left]=temp[i];
        }
    }

    public static void mergeSortnor(int[] arr){
        int gap=1;
        while(gap< arr.length){
            for (int i = 0; i < arr.length; i=i+gap*2) {
                int left=i;
                int mid=left+gap-1;
                if (mid>=arr.length){
                    mid=arr.length-1;
                }
                int right=mid+gap;
                if (right>=arr.length){
                    right=arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap*=2;
        }
    }



}



